現在ワークパーミットを取得し働いています。事情があり今の会社で思うように働けません。そこで、仕事を変えて新たにワークパーミットを取得したいと考えています。これは可能なのでしょうか？

新しい会社からLMIAを出してもらえれば、ワークパーミット申請できますよ。
私は解雇されたのでEIをもらいながら、就職活動しました。
一度発行されたワークパーミットは、会社を辞めても、有効期限内ならカナダに滞在できるそうです。
もちろん、ワークパーミット上に書かれている会社でしか働けません。
カナダ国外に出ないほうが良いです。

解雇されたら、EIはもらえないはず。

Layoff って日本語で解雇だと思ってました。失礼しました。

詳しくありがとうございます。
今の会社でせっかくワークパーミットを頂いたんですが、労働時間を減らされてしまい悩んでます。

私も最初のワークパーミットをもらった会社で思うように働けなかったので、
辞めて現在は違う会社のワークパーミットで働いてます。
現在のワークパーミットが有効な間、カナダに滞在できますが、働けるのはパーミットに記載されている雇用主に限定されますので、新たに新しい会社からのワークパーミットが必要になります。
まずLMIA取得が可能な雇用主を探し、無事発行されたら契約書を交わし、それらと申請書等をスキャンしてオンライン申請、クレジットカード決済しました。郵送より処理が早いと聞いたので。
2年前の事ですが、雇用主を見つけてLMIA発行までが2週間ほど。その後自分でオンライン申請をしてからワークパーミット発行まで1ヶ月ちょっとだったでしょうか。
イミグレのサイトで、Extend your work permit →　You are offered a different job in Canada
から申請できるはずです。
よい職場が見つかるといいですね。